#ifndef __BTREE_H__
#define __BTREE_H__

#include <string>
#include <iostream>
#include "TreeNode.h"
using namespace std;
typedef int TreeKey;


class TreeNode;

class TreeItem 
{
public:
	TreeKey mKey;
	string mData;
	TreeItem(){}
	TreeItem(TreeKey ikey,string idata)
	{
		mKey=ikey;
		mData=idata;
	}
	~TreeItem(){}
	int getKey(){return mKey;}
	string getData(){return mData;}
	void setKey(TreeKey k){mKey = k;}
	void setData(string d){mData = d;}
	void printKey(){cout << mKey <<" "<< mData;}
};

class BTree 
{
	TreeNode * Root;
	int NumOfLeaf; 

public:
	void insertItem(TreeItem *);
	void deleteItem(TreeItem *);

	TreeItem* find(TreeKey key);
	void printKeys(void); 
	void printData(void); 
	/*=====================================================*/
	BTree(){Root=NULL; NumOfLeaf=0;}
	~BTree();
	TreeNode* getRoot(){return Root;}
	void setRoot(TreeNode* node){Root = node ;}
	int GetNumOfLeaf(){return NumOfLeaf;} 
	void setLeavesNum(int num){NumOfLeaf=num;}
	/*============= insert member function ==============*/
	int Insert(int k,string d);
	void Insert_Helper(TreeNode* node);
	void add_node(TreeNode* node,TreeNode* Parent);
	void insert_child_to_parent(TreeNode* node , TreeNode* Parent);
	void Split(TreeNode* uncale ,TreeNode* node , TreeNode* Parent);
	void basic_Insert(TreeNode* node);
	/*============ Find member functions =================*/
	TreeNode* find_node_parent(TreeNode* node);
	TreeNode* findKey(int Key);
	TreeNode* find_min(TreeNode* node1,TreeNode* node2,TreeNode* node3);
	TreeNode* find_mid(TreeNode* node1,TreeNode* node2,TreeNode* node3);
	TreeNode* find_max(TreeNode* node1 , TreeNode* node2 , TreeNode* node3);
	TreeItem* Find(int k);
	int get_Lowest_Left_Key( TreeNode* node );
	/*=========== remove member function =================*/
	TreeItem* Delete(int k);
	void remove( TreeNode* node , TreeNode* parent );
	void basic_remove( TreeNode* node , TreeNode* parent , int childNum );
	int Son_Location(TreeNode* Parent,TreeNode* node);	
	/*=====================================================*/
	void updateKeys( TreeNode* node );
	void SaveInFile(ofstream &out_file, TreeNode* node);
	void PrintBTree();
	int IsEmpty();
	void PrintBTree(TreeNode* node);
	void FreeAllElements();
	/*=====================================================*/
};



#endif